As computers become more and more sophisticated, the data structures that may be employed by those computers have become larger and larger. For example, the design of a new integrated circuit, such as a microprocessor, may include the organization of millions and millions of transistors or other electrical devices into logic circuits, memory circuits, programmable field arrays, and other circuit devices. In order to allow a computer to more easily process these large data structures (and to allow human users to better understand the data structures), large data structures are often broken up into a hierarchical organization of cells. Thus, with the above example, all of the transistors making up a single memory circuit may be categorized into a single cell. Rather than having to enumerate each transistor individually, the group of transistors making up the memory device can thus collectively be referred to and operated on as a single unit. For example, when creating a data structure containing a design for a new integrated circuit, a designer can simply add a single reference for the data corresponding to the cell representing the desired memory device in one operation, rather than having to individually add the data for each transistor making up the memory device.
Typically, a data structure divided into cells will have the cells arranged in a hierarchical manner. The lowest level of cells may include only the basic elements of the data structure. A medium level of cells may then include one or more of the low-level cells, and a higher level of cells may then include one or more of the medium-level cells, and so on. Further, with some data structures, a cell may include one or more lower-level cells in addition to basic elements of the data structure. Thus, for the above example, a cell of data representing a register may include several instances of a cell of data representing a memory circuit, several instances of different cells of data representing various logic devices, and elementary data representing special-purpose connection circuitry. In turn, a cell of data representing a memory array may include several instances of the cell of data representing the register, together with elementary data representing special-purpose connection circuitry.
The division of a data structure into cells may allow tasks to be executed with the data structure more efficiently and with fewer resources. For example, data structures defining a schematic of an integrated circuit must be converted into a corresponding data structure defining the layout of the materials necessary to form the integrated circuit. In the process of translating the data structure describing the schematic (or “source” information) into a data structure describing the layout of materials, however, errors can be introduced. Accordingly, before a large amount of money is spent to make a production run or an integrated circuit based upon the translated layout data structure, the layout data structure is carefully compared with the original schematic data structure. Without dividing both of the data structures into a cellular hierarchy, an element-by-element comparison of both data structures must be made. For a very large integrated circuit, with millions and millions of transistors, such a comparison would be too long to be practical. By dividing both of the data structures into cells, however, a smaller number of data units can be compared to confirm the accuracy of the layout data structure. Thus, the comparison can be made more quickly and using fewer processing resources.
While the use of cells in data structures may allow tasks to be executed with data structures more efficiently, the use of cells themselves may introduce errors into the execution of a task. Thus, with the above example, if a cell in a schematic data structure is inadvertently compared with the incorrect cell in the layout data structure (that is, a cell that is not intended to correspond to the cell in the schematic data structure), then the comparison task will falsely indicate an error that would be avoided by an element-by-element comparison of the schematic data structure with the layout data structure. As will be appreciated by those of ordinary skill in the art, the use of some cells will be very effective in reducing a comparison the amount of processing overhead or memory use, while the use of other cells may have little impact on processing overhead or memory use. Ordinarily, however, it is difficult to determine which cells will be useful to employ in executing a task, such as a comparison operation, and which cells will not be worth employing.